class Solution {
    public int nthUglyNumber(int n) {
        int dp[] = new int[n];
        int j2 = 0, j3 = 0, j5 = 0;
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            int two = dp[j2] * 2;
            int three = dp[j3] * 3;
            int five = dp[j5] * 5;
            dp[i] = Math.min(Math.min(two, three), five);
            if (dp[i] == two) {
                j2++;
            }
            if (dp[i] == three) {
                j3++;
            }
            if (dp[i] == five) {
                j5++;
            }
        }
        return dp[n - 1];
    }
}